#include "classical-problems.h"
#include <string>
#include <set>

namespace pot {
bool Game24PointsNaive(float A[], std::string exp[], int n) {
  if (1 == n) {
    if (A[0] == 24) {
      printf("24 = %s\n", exp[0].c_str());
      return true;
    }
    return false;
  }

  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      float a = A[i];
      float b = A[j];
      std::string expa = exp[i];
      std::string expb = exp[j];

      A[j] = A[n - 1];
      exp[j] = exp[n - 1];
            
      A[i] = a + b;
      exp[i] = "(" + expa + " + " + expb + ")";
      if (pot::Game24PointsNaive(A, exp, n - 1)) return true;

      A[i] = a * b;
      exp[i] = "(" + expa + " * " + expb + ")";
      if (pot::Game24PointsNaive(A, exp, n - 1)) return true;

      A[i] = a - b;
      exp[i] = "(" + expa + " - " + expb + ")";
      if (pot::Game24PointsNaive(A, exp, n - 1)) return true;

      A[i] = b - a;
      exp[i] = "(" + expb + " - " + expa + ")";
      if (pot::Game24PointsNaive(A, exp, n - 1)) return true;

      if (b != 0) {
        A[i] = a / b;
        exp[i] = "(" + expa + " / " + expb + ")";
        if (pot::Game24PointsNaive(A, exp, n - 1)) return true;
      }

      if (a != 0) {
        A[i] = b / a;
        exp[i] = "(" + expb + " / " + expa + ")";
        if (pot::Game24PointsNaive(A, exp, n - 1)) return true;
      }

      A[i] = a;
      A[j] = b;
      exp[i] = expa;
      exp[j] = expb;
    }
  }
  return false;
}

void Game24PointsNaive(float A[]) {
  std::string exp[4];
  char buff[256];
  for (int i = 0; i < 4; ++i) exp[i] = itoa(A[i], buff, 10);
  if (!pot::Game24PointsNaive(A, exp, 4)) 
    printf("Naive: Fail^^^^^^^^^^^^^^^^^\n");  
}

typedef std::set<float> Result;

void Fork(Result S[], int k, int i, int j) {
  for (Result::const_iterator it = S[i].begin(); it != S[i].end(); ++it) {
    for (Result::const_iterator jt = S[j].begin(); jt != S[j].end(); ++jt) {
      float a = *it, b = *jt;
      S[k].insert(a + b);
      S[k].insert(a * b);
      S[k].insert(a - b);
      S[k].insert(b - a);
      if (a != 0) S[k].insert(b / a);
      if (b != 0) S[k].insert(a / b);
    }
  }
}

void F(Result S[], int k) {
  if (S[k].size() > 0) return;
  for (int x = 1; x < k; ++x) {
    if ((k & x) == x) {
      F(S, k - x);
      F(S, x);
      Fork(S, k, k - x, x);
    }
  }
}

void Game24Points(float A[]) {
  Result S[16];
  
  for (int i = 0; i < 4; ++i)  S[1 << i].insert(A[i]);

  pot::F(S, 0xF);

  if (S[0xF].find(24) != S[0xF].end())
    printf("OK******************\n");
  else 
    printf("Fail^^^^^^^^^^^^^^^^^\n");

  //printf("\n**********************************\n");
}

void Game24PointsTest() {
  float A[4];
  float B[4];
  for (int i = 0; i < 100; ++i) {
    for (int j = 0; j < 4; ++j) {
      A[j] = rand() % 13 + 1;
      B[j] = A[j];
    }
    pot::Game24PointsNaive(A);
    pot::Game24Points(B);
    printf("-----------------------------------------\n");
  }
}

} // pot
